// https://leetcode.cn/problems/pacific-atlantic-water-flow/description/

// 算法思路总结：
// 1. 逆向思维：从两大洋边界开始DFS/BFS反向标记可流入区域
// 2. 太平洋边界：第一行和第一列，标记pvis数组
// 3. 大西洋边界：最后一行和最后一列，标记avis数组
// 4. 水从低处流向高处（heights[x][y] >= heights[a][b]）
// 5. 最终取两个标记数组的交集作为结果
// 6. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    int m, n;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    vector<vector<int>> ret;
    bool pvis[201][201], avis[201][201];

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) 
    {
        m = heights.size(), n = heights[0].size();
        ret.clear();
        memset(pvis, 0, sizeof(pvis));
        memset(avis, 0, sizeof(avis));

        for (int i = 0 ; i < m ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                if ((i == 0 || j == 0) && pvis[i][j] == false)
                {
                    pvis[i][j] = true;
                    dfs(heights, i, j, pvis);
                }
                if ((i == m - 1 || j == n - 1) && avis[i][j] == false)
                {
                    avis[i][j] = true;
                    dfs(heights, i, j, avis);
                }
            }
        }

        for (int i = 0 ; i < m ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                if (pvis[i][j] == true && avis[i][j] == true)
                {
                    ret.push_back({i, j});
                }
            }
        }

        return ret;
    }

    void dfs(vector<vector<int>>& heights, int a, int b, bool(&vis)[201][201])
    {
        for (int i = 0 ; i < 4 ; i++)
        {
            int x = a + dx[i], y = b + dy[i];
            if (x >= 0 && y >= 0 && x < m && y < n && vis[x][y] == false && heights[x][y] >= heights[a][b])
            {
                vis[x][y] = true;
                dfs(heights, x, y, vis);
            }
        }
    }

    void printResult(const vector<vector<int>>& result) 
    {
        cout << "[";
        for (int i = 0; i < result.size(); ++i) 
        {
            cout << "[";
            for (int j = 0; j < result[i].size(); ++j) 
            {
                cout << result[i][j];
                if (j < result[i].size() - 1) cout << ",";
            }
            cout << "]";
            if (i < result.size() - 1) cout << ",";
        }
        cout << "]" << endl;
    }   
};

int main()
{
    vector<vector<int>> heights1 = {
        {1, 2, 2, 3, 5},
        {3, 2, 3, 4, 4},
        {2, 4, 5, 3, 1},
        {6, 7, 1, 4, 5},
        {5, 1, 1, 2, 4}
    };

    vector<vector<int>> heights2 = {
        {2, 1},
        {1, 2}
    };

    Solution sol;

    auto vv1 = sol.pacificAtlantic(heights1);
    auto vv2 = sol.pacificAtlantic(heights2);

    sol.printResult(vv1);
    sol.printResult(vv2);

    return 0;
}